#include<bits/stdc++.h>
using namespace std;
const int N=305;
const int T=1002;

int m;
bool visit[N][N];
bool fexist[N][N];
bool exist[N][N];
int dx[5]={0,1,0,-1,0};
int dy[5]={-1,0,1,0,0};

vector<int> xy[T];
int tmax=0;

int main()
{
	memset(fexist,true,sizeof(fexist));
	memset(exist,true,sizeof(exist));
	
	scanf("%d",&m);
	int x,y,t;
	int x1,y1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&t);
		tmax=max(tmax,t);
		for(int j=0;j<5;j++)
		{
			x1=x+dx[j];
			y1=y+dy[j];
			if(x1>=0&&y1>=0)
			{
				xy[t].emplace_back(x1);
				xy[t].emplace_back(y1);
				fexist[x1][y1]=false;
				if(t==0)
				{
					exist[x1][y1]=false;
				}
			}
		}
	}
	
	if(fexist[0][0])
	{
		printf("0");
		return 0;
	}
	if(!exist[0][0])
	{
		printf("-1");
		return 0;
	}
	
	queue<int> que;
	que.push(0);
	que.push(0);
	for(t=1;t<=tmax+1&&!que.empty();t++)
	{
		for(int i=0;i<xy[t].size();i+=2)
		{
			x=xy[t][i];
			y=xy[t][i+1];
			for(int j=0;j<5;j++)
			{
				x1=x+dx[j];
				y1=y+dy[j];
				if(x1>=0&&y1>=0) exist[x1][y1]=false;
			}
		}
		//
		memset(visit,false,sizeof(visit));
		int size=que.size()/2;
		for(int i=0;i<size;i++)
		{
			x=que.front();que.pop();
			y=que.front();que.pop();
			for(int j=0;j<4;j++)
			{
				x1=x+dx[j];
				y1=y+dy[j];
				if(x1<0||y1<0) continue;
				if(fexist[x1][y1])
				{
					printf("%d",t);
					return 0;
				}
				if(exist[x1][y1]&&!visit[x1][y1])
				{
					visit[x1][y1]=true;
					que.push(x1);
					que.push(y1);
				}
			}
		}
	}
	printf("-1");
	return 0;
}
